package problem373;

//373.查找和最小的 K 对数字
//https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/?envType=study-plan-v2&envId=top-interview-150

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->(
            nums1[a[0]] + nums2[a[1]] - (nums1[b[0]] + nums2[b[1]])
        ));
        int n = nums1.length, m = nums2.length;
        for(int i = 0; i<Math.min(n, k); i++) {
            queue.add(new int[]{i, 0});
        }
        List<List<Integer>> ret = new ArrayList<>();
        while(k-- > 0 && !queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int[] t = queue.poll();
            list.add(nums1[t[0]]);
            list.add(nums2[t[1]]);
            ret.add(list);
            if(t[1] + 1 < m) {
                queue.add(new int[]{t[0], t[1]+1});
            }
        }
        return ret;
    }
}